package com.tree.leetcode.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @ClassName com.tree.leetcode.array
 * Description: 56. 合并区间
 * <p>
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。



示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
 * </p>
 * @Author tree
 * @Date 1/27/24 11:17 AM
 * @Version 1.0
 */
public class Merge_56 {
    public static void main(String[] args) {
        int [][] intervals = new int[][]{{1,3},{2,6},{15,18},{8,10}};
        System.out.println(merge(intervals));
    }

    /**
    参考：https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC
     */
    public static int[][] merge(int[][] intervals) {
        List<int[]> res = new LinkedList<>();

        //按每个数组的左边界排序
        Arrays.sort(intervals, (x,y)->Integer.compare(x[0],y[0]));
        //初始化第一个数组， 左边界为第0行第0列[0][0], 右边界为第0行第1列[0][1]
        int startBound = intervals[0][0];
        int rightBound = intervals[0][1];
        //从1开始， 需要把第i行的第0列（首）[i][0]与第i-1行的第1列（尾）比较[i-1][1]
        for(int i =1 ;i < intervals.length; i++){
            //如果小于， 则代表有重合， 则需要合并这两个数组， 左边界不动， 右边界取两个数组的最大值
            if(intervals[i][0] < rightBound){
                rightBound = Math.max(intervals[i][1], rightBound);
            }else {//如果没有重合， 加入新区间， 并且更新start
                res.add(new int[]{startBound,rightBound});
                startBound = intervals[i][0];
                rightBound = intervals[i][1];

            }
        }
        res.add(new int[]{startBound,rightBound});
        return  res.toArray(new int[res.size()][2]);

    }


}
